/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sliding-window-unique-elements-sum
   @Language: C++
   @Datetime: 19-06-25 09:37
   */

class Solution {
public:
	/**
	 * @param nums: the given array
	 * @param k: the window size
	 * @return: the sum of the count of unique elements in each window
	 */
	int slidingWindowUniqueElementsSum(vector<int> &nums, int k) {
		// write your code here
		if(nums.size()<k) return 1;
		unordered_map<int,int> freqs;
		for(int i=k; i--; ++freqs[nums[i]]);
		int cnt=0;
		for(const auto &freq:freqs)
			cnt+=freq.second==1;
		for(int i=0; i+k<nums.size(); ++i){
			--freqs[nums[i]];
			++freqs[nums[i+k]];
			if(freqs[nums[i]]==0) freqs.erase(nums[i]);
			for(const auto &freq:freqs)
				cnt+=freq.second==1;
		}
		return cnt;
	}
};
